package com;

import java.awt.*;
import java.util.Arrays;

/**
 * 11. 盛最多水的容器
 * 给你 n 个非负整数 a1，a2，...，an，每个数代表坐标中的一个点 (i, ai) 。在坐标内画 n 条垂直线，垂直线 i 的两个端点分别为 (i, ai) 和 (i, 0) 。找出其中的两条线，使得它们与 x 轴共同构成的容器可以容纳最多的水。
 * <p>
 * 说明：你不能倾斜容器。
 * <p>
 * 来源：力扣（LeetCode）
 * 链接：https://leetcode-cn.com/problems/container-with-most-water
 * 著作权归领扣网络所有。商业转载请联系官方授权，非商业转载请注明出处。
 *
 * @author 罗俊华
 * @date 2021/7/23 - 9:02 上午
 */
public class TheContainerWithTheMostWater {

    public static void main(String[] args) {
        long currentTimeMillis = System.currentTimeMillis();
        int[] arr = {1, 8, 6, 2, 5, 4, 8, 3, 7};

        int i = new TheContainerWithTheMostWater().maxArea(arr);
//        最多能盛水：4913370，总共耗时：19283

        System.out.printf("最多能盛水：%s，总共耗时：%d", i, System.currentTimeMillis() - currentTimeMillis);

    }

    public int maxArea(int[] height) {

        int l = 0, h = height.length - 1;
        int area = 0;
        int maxHeight = 0;
        while (l < h) {

            area = Math.max(area, (h - l) * Math.min(height[l], height[h]));

            if (height[l] > height[h]) {
                h--;
            } else {
                l++;
            }
        }


        return area;
    }


    @Deprecated
    public int maxArea2(int[] height) {

        int[][] cache = new int[height.length][];
        for (int i = 0; i < cache.length; i++) {

            int[] c = new int[height.length];

            Arrays.fill(c, -1);

            cache[i] = c;
        }


        return getMaxArea(height, cache);
    }

    private int getMaxArea(int[] height, int[][] cache) {

        // 从原点到指定index的最大面积
        int zeroToIndexMaxArea = 0;

        int minHeight = 0;

        int maxArea = 0;

        int rightStartIndex = 0;

        for (int i = 0; i < height.length; i++) {

            zeroToIndexMaxArea = 0;

            for (int left = 0; left < i; left++) {

                for (int right = i - left; right <= i; right++) {

                    minHeight = Math.min(height[left], height[right]);

                    zeroToIndexMaxArea = Math.max(zeroToIndexMaxArea, (right - left) * minHeight);
                }
//                }
            }

            maxArea = Math.max(maxArea, zeroToIndexMaxArea);

        }
        return maxArea;

    }
}
